#define  _CRT_SECURE_NO_WARNINGS
class Solution {
    int row[9][10] = { 0 };
    int col[9][10] = { 0 };
    int center[3][3][10] = { 0 };
    void init(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.') continue;
                int cur = board[i][j] - '0';
                row[i][cur] = col[j][cur] = center[i / 3][j / 3][cur] = true;
            }
        }
    }
    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    for (char n = '1'; n <= '9'; n++)
                    {
                        board[i][j] = n;
                        int cur = board[i][j] - '0';

                        if (row[i][cur] || col[j][cur] || center[i / 3][j / 3][cur]) continue;
                        row[i][cur] = col[j][cur] = center[i / 3][j / 3][cur] = true;

                        if (dfs(board)) return true;
                        row[i][cur] = col[j][cur] = center[i / 3][j / 3][cur] = false;
                    }
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        init(board);
        dfs(board);
    }
};